public class code3 {

    // top 101 旋转数组中的最小数字
    // 这道题还是很值得多思考思考的

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // 这里可以将数组分解为两部分
        // 这两部分均为 从小到大排序的数组，以 12345 为例
        // 会有 34512、45123 等

        // write code here
        // 先来判断一下数组为空的情况
        if(nums.length == 0) {
            return 0;
        }

        // 使用二分法来解决
        int start = 0;
        int end = nums.length - 1;
        // 这里是旋转数组，先来考虑第一种情况
        // 当这里的第一个元素的值 比 最后一个元素的值小
        // 对于上面的例子，可以断定这里的第一个值 就一定是 最小值
        if(nums[start] < nums[end]) {
            return nums[start];
        }

        // 之后通过 二分法来判断最小值
        // 先来说明没有重复值的情况
        // 不断的通过 左、右 侧加逼
        // 最终会使得 start 在左侧部分的最大值(最后一个位置) 上
        // 并且会使得 end 在右侧部分上达到其中的 最小值(这个就是我们需要的值)
        // 此时 start 和 end 就是一个相邻的关系，所以对于 while 设定这样一个判断条件
        while(start != end-1) {
            int mid = (start + end) / 2;
            // 在这之中还需要处理多个重复数据的情况，并且处理三个指针重叠后的情况
            // 如题例：1,0,1,1,1
            if(nums[start] == nums[end] && nums[start] == nums[mid]) {
                // 这里定义一个方法专门来处理这个问题
                return minNum(nums,start,end);
            }
            if(nums[mid] >= nums[start]) {
                start = mid;
            }else if(nums[mid] <= nums[end]){
                end = mid;
            }
        }
        // 在完成上面的判断后，这里的 end 位置的值就是我们要找到的最小值
        return nums[end];
    }

    private int minNum(int[] nums, int start, int end) {
        // 这里需要注意的是，要将值设置为 当前重合处的值，不能设置为 0 ！！！
        int re = nums[start];
        for (int i=0; i < nums.length; i++) {
            if(re > nums[i]) {
                // 将这里的最小值记录下来并返回
                re = nums[i];
            }
        }
        return re;
    }
}
